#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cassert>
#define DEBUG_LEVEL 6
#include <debug_func.h>
#include <iostream>

#include <boost/config.hpp>
//#include <boost/algorithm/string.hpp>


#include <boost/graph/transpose_graph.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>


#include <boost/regex.hpp>
#include <boost/foreach.hpp>
#include <print_error.h>
#include <tab_delimited_file_to_map.h>
#include "get_arg.h"
using std::cerr;
using std::cout;
using std::string;
using std::vector;
using std::pair;
using std::deque;
using std::ostream;


template <typename OutputIterator>
class back_edge_recorder : public boost::default_dfs_visitor
{
public:
	back_edge_recorder(OutputIterator out) : m_out(out){	}
	template <typename Edge, typename Graph>
		void tree_edge(Edge e,  const Graph& g) 
	{
		std::cout
			<< get(boost::vertex_name, g, source(e, g))
			 << "->"
			<< get(boost::vertex_name, g, target(e, g))
			<< "\n";
		intermediate_node = true;
		*m_out++ = e;
	}
	template <typename t_vertex, typename Graph>
		void discover_vertex(t_vertex v,  const Graph& g) {std::cout << "+" << get(boost::vertex_name, g, v) << "\n";intermediate_node = false;}
	template <typename t_vertex, typename Graph>
		void finish_vertex(t_vertex v,  const Graph& g) {std::cout << "-" << get(boost::vertex_name, g, v) << "\n";
		if (!intermediate_node) std::cout << get(boost::vertex_name, g, v) << " is a leaf\n"; intermediate_node = true;}
private:
	OutputIterator m_out;
	bool intermediate_node;
};

template <typename OutputIterator>
back_edge_recorder<OutputIterator>
make_back_edge_recorder(OutputIterator out)
{
	return back_edge_recorder<OutputIterator>(out);
}

int main (int argc, char *argv[])
{


	t_program_args args;

	try
	{

		debug_func_cerr(5);

		// don't use C streams
		std::ios::sync_with_stdio(false);


		// get command line arguments
		if (!process_command_line_options(argc, argv, args))
			return 1;


		using boost::adjacency_list;
		using boost::vecS;
		using boost::undirectedS;
		using boost::bidirectionalS;
		using boost::property;
		using boost::vertex_name_t;
		using boost::property_map;
		using boost::graph_traits;
		using boost::vertex_name;
		using boost::tie;
		using boost::default_color_type;
		using boost::vertex_color_t;
		using boost::vertex_color;
		typedef int weight_t;
		typedef adjacency_list < vecS, vecS, undirectedS,
								// vertex properties
								property < vertex_name_t, char,
									property< vertex_color_t,  default_color_type> >
									 > t_graph;

		enum
		{
			a, b, c, d, e, f, g, N
		};
		t_graph G(N);
		property_map < t_graph, vertex_name_t >::type
		name_map = get(vertex_name, G);
		char name = 'a';
		graph_traits < t_graph >::vertex_iterator v, v_end;
		for (tie(v, v_end) = vertices(G); v != v_end; ++v, ++name)
			name_map[*v] = name;

		typedef std::pair < int, int >E;
		E edge_array[] = { E(c, f), E(c, a), E(a, b), E(b, e), E(b, d), 
			E(c, g)
		};
		for (unsigned i = 0; i < sizeof(edge_array) / sizeof(E); ++i)
			add_edge(edge_array[i].first, edge_array[i].second, G);
		typedef boost::graph_traits<t_graph>::edge_descriptor t_edge;
		typedef boost::graph_traits<t_graph>::vertex_descriptor t_vertex;
		typedef boost::color_traits<default_color_type> t_color;

		typedef boost::property_map<t_graph, vertex_color_t>::type color_map_t;
		color_map_t color_map = get(vertex_color,  G);
		for (tie(v, v_end) = vertices(G); v != v_end; ++v)
			put(color_map, *v, t_color::white());
		
		for (tie(v, v_end) = vertices(G); v != v_end; ++v)
		{
			if (name_map[*v] == 'a')
				break;
		}


		std::vector<t_edge> back_edges;

		boost::depth_first_visit(G, 
								  *v,
								  make_back_edge_recorder(std::back_inserter(back_edges)),
								 get(vertex_color,  G));

		{
			std::vector<t_edge>::iterator ei = back_edges.begin();
			std::vector<t_edge>::iterator ei_end = back_edges.end();
			for (; ei != ei_end; ++ei)
				std::cout << boost::get(name_map,source(*ei,G)) << "->"
							<< boost::get(name_map,target(*ei,G)) << "!\n";
		}	

		
		print_graph(G, name_map);
		std::cout << std::endl;

		t_graph G_T;
		transpose_graph(G, G_T);

		print_graph(G_T, name_map);

		graph_traits < t_graph >::edge_iterator ei, ei_end;
		for (tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
			assert(edge(target(*ei, G), source(*ei, G), G_T).second == true);
		args.VERBOSE() << "\tAll finished.\n";
	}
	catch (std::exception& e)
	{
		std_print_error(args.CERR(), e.what());
		return 1;
	}

	return 0;


}


